#include <vector>
using std::vector;

#include <utility>
using std::swap;

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

template <class T>
class heap
{
public:
    heap()
        : m_array(nullptr)
        , m_size(0)
        , m_capacity(0)
    {
        
    }

    // 建小堆 
    heap(const vector<T>& v)
    {
        m_size = v.size();
        m_capacity = m_size;
        m_array = new T[m_size];
        for (int i = 0; i < m_size; ++i)
        {
            m_array[i] = v[i];
        }

        // 从最后一个非叶节点开始向根节点的方向进行扫描
        for (int cur_pos = (m_size - 1 - 1) / 2; cur_pos >= 0; --cur_pos)
        {
            // 检查该节点是否在正确的位置
            T cur = m_array[cur_pos];
            int i = cur_pos;
            int min_child_pos = i * 2 + 1;
            while (min_child_pos < m_size) // i位置没有孩子, 也就不用再向下找了
            {
                if (min_child_pos + 1 < m_size && m_array[min_child_pos] > m_array[min_child_pos + 1])
                {
                    ++min_child_pos;
                }

                if (m_array[min_child_pos] > cur)
                {
                    // 说明该位置(即i位置)为正确位置, 注意每次进入循环都有一个i
                    // 这个i代表的是一个位置
                    // 还有每次进入循环, 只有i位置, 这个位置为空
                    break;
                }
                else
                {
                    // 如果不是正确位置, 就继续找
                    swap(m_array[i], m_array[min_child_pos]); // 为什么使用swap会导致内存超限
                    i = min_child_pos;
                    min_child_pos = i * 2 + 1;
                }

            }

            //m_array[i] = cur;
        }
    }

    void reserve(int new_capacity)
    {
        if (new_capacity > m_capacity)
        {
            T* tmp = new T[new_capacity];
            for (int i = 0; i < m_size; ++i)
            {
                swap(tmp[i], m_array[i]);
            }
            m_capacity = new_capacity;
            delete[] m_array;
            m_array = tmp;
        }
    }

    void push(const T& x)
    {
        if (m_size == m_capacity)
        {
            // 扩容
            int new_capacity = m_capacity == 0 ? 4 : 2 * m_capacity;
            reserve(new_capacity);
        }

        m_array[m_size] = x;
        ++m_size;

        // 检查该位置是否为正确位置, 为调整为堆
        int cur_pos = m_size - 1;
        int parent_pos = (cur_pos - 1) / 2;
        while (cur_pos > 0)
        {
            if (m_array[cur_pos] < m_array[parent_pos])
            {
                swap(m_array[cur_pos], m_array[parent_pos]);
                cur_pos = parent_pos;
                parent_pos = (cur_pos - 1) / 2;
            }
            else
            {
                break;
            }
        }


        // while (m_array[cur_pos] < m_array[parent_pos]) // 小的要在上面
        // {
        //     swap(m_array[cur_pos], m_array[parent_pos]);
        //     cur_pos = parent_pos;
        //     parent_pos = (cur_pos - 1) / 2;
        // }
    }

    void pop()
    {
        if (m_size == 0)
        {
            return;
        }

        //m_array[0].~T();
        //T cur = m_array[m_size - 1];
        swap(m_array[m_size - 1], m_array[0]);
        //m_array[m_size - 1].~T();
        --m_size; 
        
        int cur_pos = 0;
        int min_child_pos = cur_pos * 2 + 1;
        while (min_child_pos < m_size) // 判断是否为叶节点
        {
            // 最小孩子
            if (min_child_pos + 1 < m_size && m_array[min_child_pos] > m_array[min_child_pos+1])
            {
                ++min_child_pos;
            }

            if (m_array[min_child_pos] >= m_array[cur_pos])
            {
                break;
            }
            else
            {
                swap(m_array[cur_pos], m_array[min_child_pos]);
                //m_array[cur_pos] = m_array[min_child_pos];
                cur_pos = min_child_pos;
                min_child_pos = cur_pos * 2 + 1;
            }
        }
        //m_array[cur_pos] = cur; // 必须要放在外边, 因为叶节点进不去
    }

    T& top()
    {
        return m_array[0];
    }

    int size()
    {
        return m_size;
    }

private:
    T* m_array;
    int m_size;
    int m_capacity;
};